package com.fr.lintcode;

import org.junit.Test;

public class Q1399ii {
    /**
     * @param list:
     *            The coins
     * @param k:
     *            The k
     * @return: The answer
     */
    // 贪心算法 不对
    public int takeCoins(int[] list, int k) {
        // Write your code here
        if (list == null || list.length == 0 || k == 0) {
            return 0;
        }
        int length = list.length;
        int l = 0;
        int r = length - 1;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            if (list[l] > list[r]) {
                sum += list[l];
                l++;
            } else if (list[l] < list[r]) {
                sum += list[r];
                r--;
            } else {
                if (chooseLeft(list, l, r)) {
                    sum += list[l];
                    l++;
                } else {
                    sum += list[r];
                    r--;
                }
            }
        }
        return sum;
    }

    private boolean chooseLeft(int[] list, int left, int right) {
        while (left > right) {
            if (list[left] > list[right]) {
                return true;
            } else if (list[left] < list[right]) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

    @Test
    public void testA() {
        int[] list = {1225, 3287, 3472, 3015, 2204, 915, 7613, 4255, 971, 5662, 7453, 793, 1662, 181, 7946, 8184, 425,
            3784, 5160, 4757, 3094, 8170, 1877, 5502, 7653, 5020, 1924, 7665, 4288, 6717, 9546, 9466, 2916, 2331, 7640,
            4601, 9084, 5517, 7146, 9047, 5120, 8756, 7743, 43, 4911, 9518, 1979, 2520, 4905, 8781, 7433, 4121, 2496,
            8712, 5845, 4063, 2047, 3793, 841, 1274, 4364, 8183, 9990, 4471, 1210, 3324, 4517, 7913, 2738, 1626, 2222,
            4251, 5843, 8705, 8185, 1589, 7927, 7892, 8356, 8061, 2120, 6965, 9188, 2383, 1026, 7790, 3679, 9392, 8891,
            9281, 810, 4112, 9425, 962, 5358, 8734, 7491, 9236, 1696, 8992, 3859, 7041, 7633, 1987, 6042, 8383, 1747,
            880, 2557, 6255, 8574, 5744, 9150, 375, 2498, 5361, 6037, 1538, 7309, 7737, 4241, 5350, 4591, 3946, 521,
            5191, 3435, 3703, 1144, 1178, 7425, 9590, 1993, 5164, 4139, 1558, 3855, 8180, 2053, 8003, 2889, 6695, 5632,
            4760, 3843, 3035, 9016, 2437, 8192, 5085, 1861, 8065, 2775, 5079, 8367, 5953, 3084, 2140, 9670, 1849, 7408,
            7782, 2304, 562, 1691, 6690, 9540, 9901, 6041, 9402, 7846, 3223, 4627, 1364, 8500, 862, 5440, 9881, 5521,
            5939, 4236, 3000, 3968, 5904, 1639, 6299, 3444, 9948, 320, 4843, 9317, 6668, 6756, 1360, 4821, 173, 3586,
            3451, 9299, 3903, 4593, 2568, 4688, 1444, 1252, 2478, 3184, 5289, 7340, 601, 2212, 5604, 5919, 8842, 4534,
            5039, 9368, 7756, 708, 5924, 5983, 7466, 3600, 2682, 3819, 8976, 5815, 6862, 8853, 4575, 1457, 1477, 2894,
            182, 4329, 2209, 6787, 621, 6125, 5842, 5408, 4099, 568, 3039, 3843, 74, 430, 5814, 6963, 7409, 8936, 5744,
            7137, 7011, 9713, 2664, 157, 3070, 5711, 942, 1980, 7559, 7254, 7095, 4024, 1195, 2570, 2471, 1337, 9209,
            803, 3041, 2435, 191, 5494, 29, 9151, 1458, 4498, 1292, 9583, 5202, 2024, 8681, 4156, 541, 1886, 3185, 7026,
            1906, 1125, 132, 767, 9961, 3898, 3484, 760, 1009, 8634, 6589, 8316, 4490, 6666, 6733, 9837, 8981, 4246,
            4694, 764, 6121, 9384, 1098, 4852, 295, 3451, 1415, 7962, 719, 320, 1835, 2611, 3588, 2721, 4025, 791, 2174,
            8405, 1628, 4501, 9775, 8563, 796, 6150, 2777, 1898, 5023, 9798, 5949, 1968, 6401, 6449, 4486, 5401, 3111,
            9018, 2760, 123, 2497, 18, 3043, 1183, 7230, 3719, 2045, 1819, 2388, 6475, 2958, 990, 9072, 7415, 8557,
            9051, 5963, 2111, 8748, 8954, 4270, 359, 6864, 619, 5319, 1750, 5347, 9901, 9004, 794, 189, 5758, 3423,
            3405, 8608, 7683, 9011, 695, 9347, 9322, 5166, 7251, 1138, 7838, 8848, 4758, 403, 6380, 8675, 1245, 7148,
            6259, 4627, 4791, 5636, 5585, 7327, 2756, 327, 1740, 8705, 8587, 3854, 4733, 4795, 674, 8574, 6228, 5074,
            4201, 4015, 9560, 5871, 8632, 5600, 2174, 7779, 7019, 346, 7484, 1851, 4682, 8322, 3742, 7269, 4990, 930,
            1832, 2946, 7169, 1114, 2973, 3165, 2198, 4243, 8240, 4618, 457, 9701, 7497, 4338, 2903, 4858, 907, 6494,
            9441, 3602, 5955, 3714, 1613, 1560, 8883, 5820, 4094, 2676, 64, 1629, 853, 7859, 9449, 1800, 2168, 4996,
            9929, 4360, 1122, 8292, 895, 8311, 3002, 1581, 908, 2284, 9625, 6058, 7932, 8132, 9046, 7998, 7112, 2756,
            116, 4742, 4987, 1086, 4463, 1756, 9860, 8163, 8131, 3517, 3644, 1992, 9310, 4861, 4905, 8059, 1783, 4922,
            9665, 8696, 5262, 6638, 4611, 2647, 1349, 6553, 6482, 9288, 7360, 6174, 5076, 7570, 3801, 9804, 5322, 24,
            8551, 1633};
        int k = 217;

        int sum = takeCoins(list, k);
        System.out.println(sum);

    }
}
